0% completed
Problem Statement
Given root of two binary trees root1 and root2, return true if they are isomorphic. Otherwise, return false.
Two trees are said to be isomorphic if one tree can be transformed into the other by swapping the left and right children of some nodes.
Note that the structure should be identical after possible swaps, and the values of nodes must be the same in both trees.
Examples
Example 1
- Input: root1 =
[1, 2, 3, 4], root2 =[1, 3, 2, null, null, 4]
- Output:
true - Explanation: In the first tree, we can swap 2 with 3, and 4 with null to get the second tree by swapping.
Example 2
- Input: root1 =
[1, 2, 3], root2 =[1, 3, 2]
- Output:
true - Explanation: We can swap the left and right children of the root node in Tree 1. This transforms Tree 1 into Tree 2.
Example 3
- Input: root1 =
[1, 2, 3, 4, 5, 6, 7], root2 =[1, 4, 3, 2, 5, 7, 6]
- Output:
false - Explanation: We can't get tree2 by performing swap operations in tree1.
Solution
To solve this problem, we will use Depth-First Search (DFS) to compare both trees node by node. The key is to check if the current nodes in both trees match and then recursively verify their children. If they can be swapped and still match, the trees are isomorphic. Our approach focuses on exploring both possibilities: when the left children match with the left children, and when the left children match with the right children (after a swap). This approach is effective as it directly handles the recursive nature of trees and the swap condition, ensuring that we cover all potential transformations.
DFS ensures that we explore all nodes and their children thoroughly. This is important because both the structure and values of the trees must match after considering possible swaps at each node.
Step-by-Step Algorithm
-
Base Case 1:
- Check if both
root1androot2arenull. - If both trees are empty, return
truebecause two empty trees are considered isomorphic.
- Check if both
-
Base Case 2:
- Check if either
root1orroot2isnull. - If one tree is empty and the other is not, return
falsebecause one tree being non-existent makes them non-isomorphic.
- Check if either
-
Compare Node Values:
- Compare the values of the current nodes (
root1.valandroot2.val). - If their values do not match, return
falsebecause nodes with different values cannot be considered isomorphic.
- Compare the values of the current nodes (
-
Recursive Check without Swap:
- Check if the left child of
root1is isomorphic to the left child ofroot2and the right child ofroot1is isomorphic to the right child ofroot2. - This is the scenario where no swapping occurs. Call the
isIsomorphic()function recursively for both left and right subtrees.
- Check if the left child of
-
Recursive Check with Swap:
- Check if the left child of
root1is isomorphic to the right child ofroot2and the right child ofroot1is isomorphic to the left child ofroot2. - This is the scenario where swapping occurs. Call the
isIsomorphic()function recursively with swapped children.
- Check if the left child of
-
Final Check:
- If either of the checks (with or without swap) returns
true, then the trees are isomorphic. Returntrue. - If both checks return
false, then the trees are not isomorphic. Returnfalse.
- If either of the checks (with or without swap) returns
Algorithm Walkthrough
Example Input:
root1 = [1, 2, 3, 4]root2 = [1, 3, 2, null, null, null, 4]
-
Step 1: Start by comparing the root nodes of both trees:
root1.val = 1root2.val = 1- Since the values are equal, we proceed to check the children.
-
Step 2: First, we try comparing the children without any swaps:
- Compare
root1.left(value 2) withroot2.left(value 3).- Check 1:
2 != 3, so the comparison without swaps fails.
- Check 1:
- Compare
root1.right(value 3) withroot2.right(value 2).- Check 2:
3 != 2, so the comparison without swaps fails completely.
- Check 2:
- Compare
-
Step 3: Since comparing without swaps failed, we now try comparing the trees with a swap:
- Compare
root1.left(value 2) withroot2.right(value 2).- Check 3:
2 == 2, so the values match. Now, we need to compare their respective children.
- Check 3:
- Compare
-
Step 4: Now, compare the subtrees of
root1.leftandroot2.right. Start by comparing without swap for this subtree:- Compare
root1.left.left(value 4) withroot2.right.left(null).- Check 4:
4 != null, so the comparison without swap for this subtree fails.
- Check 4:
- Compare
-
Step 5: Since the comparison without swap for the subtree failed, we now swap the children and try again:
- Compare
root1.left.left(value 4) withroot2.right.right(value 4).- Check 5:
4 == 4, so the values match. Now, compare their children.- Both
root1.left.left.leftandroot2.right.right.leftarenull. - Both
root1.left.left.rightandroot2.right.right.rightarenull.
- Both
- Since both children are
null, this subtree returnstrue.
- Check 5:
- Compare
-
Step 6: Next, compare the right child of
root1.leftand left child ofroot2.right:- Both
root1.left.rightandroot2.right.leftarenull. - Check 6: Since both children are
null, this subtree returnstrue.
- Both
-
Step 7: Since the left and right subtrees of
root1.leftandroot2.rightmatch after the swap, the recursive check with swap for this subtree returnstrue. -
Step 8: Now, compare the right child of
root1and left child ofroot2:- Compare
root1.right(value 3) withroot2.left(value 3). - Check 7:
3 == 3, so the values match. Now, compare their children.- Both
root1.right.leftandroot2.left.leftarenull. - Both
root1.right.rightandroot2.left.rightarenull.
- Both
- Check 8: Since both children are
null, this subtree returnstrue.
- Compare
-
Final Step: Since the recursive check with swap for the left children and the comparison of the right children return
true, the final result is:- The two trees are isomorphic, so the function returns
true.
- The two trees are isomorphic, so the function returns
Code
Complexity Analysis
Time Complexity
- Each node of both trees is visited once. At each node, we perform a constant amount of work (comparisons and recursive calls).
- Therefore, the time complexity of the solution is
, where N1andN2are the number of nodes inroot1androot2respectively. - This is because we are traversing both trees simultaneously, and the traversal will stop once we reach the end of the smaller tree.
Space Complexity
- The space complexity is determined by the depth of the recursion stack.
- In the worst case (for highly unbalanced trees), the depth of recursion could be the height of the tree, leading to
space complexity, where H1andH2are the heights ofroot1androot2, respectively. - For balanced trees, the height is logarithmic, so the space complexity is
in the best case.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity